Đồ thị hai phía
Đồ thị hai phía

Đồ thị hai phía

Trong Lý thuyết đồ thị, đồ thị hai phía (đồ thị lưỡng phân hay đồ thị hai phần) (tiếng Anh: bipartite graph) là một đồ thị đặc biệt, trong đó tập các đỉnh có thể được chia thành hai tập không giao nhau thỏa mãn điều kiện không có cạnh nối hai đỉnh bất kỳ thuộc cùng một tập.Những tính chất của đồ thị hai phía được đề cập đến đầu tiên bởi Dénes Kőnig(1916) [1][2][3]. Dénes Kőnig cũng là người viết cuốn sách đầu tiên Theorie der endlichen und unendlichen Graphen 1936 [4] về Lý thuyết đồ thị.Đồ thị hai phía xuất hiện trong các bài toán dùng đồ thị biểu diễn quan hệ hai ngôi giữa hai tập A và tập B không giao nhau. Một ví dụ cho quan hệ này là quan hệ hôn nhân giữa hai tập hợp người nam và nữ.